package classic

/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 * 示例 1：
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 *
 * 示例 2：
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
fun longestCommonPrefix(strs: Array<String>): String {
    if (strs.isEmpty()) return ""
    val str = strs.minBy { it.length }
    val chars = str.toCharArray()
    val ans = StringBuilder()
    for (index in chars.indices) {
        val c = chars[index]
        for (item in strs) {
            if (item[index] != c) {
                return ans.toString()
            }
        }
        ans.append(c)
    }
    return ans.toString()
}

fun longestCommonPrefix2(strs: Array<String>): String {
    val len = strs.size
    if (len < 2) return strs[0]
    val ans = StringBuilder()
    val base = strs[0]
    for (index in base.indices) {
        val c = base[index]
        for (item in strs) {
            if (index >= item.length || item[index] != c) {
                return ans.toString()
            }
        }
        ans.append(c)
    }
    return ans.toString()
}


fun main() {
    val strs1 = arrayOf("flower", "flow", "flight")
    val strs2 = arrayOf("dog", "racecar", "car")
    println(longestCommonPrefix(strs1))
    println(longestCommonPrefix(strs2))
}
